package com.coder.algorithm.offer_2;

import java.util.Locale;

/**
 * 正则表达式匹配
 *
 * @author yuhushuan
 * @date 2020/6/14 23:54
 */
public class _19_1_RegularExpressionsMatching {
    private static String format = "";

    public static void main(String[] args) {
        print("aaa", "a.a");
        print("aaa", "ab*ac*a");
        print("aaa", "aa.a");
        print("aaa", "ab*a");
        print("aaa", "aa*a");
        print("aaa", "aa*aa");
        print("aaa", "a*");
    }

    private static void print(String str, String pattern) {
        System.out.println(String.format(Locale.getDefault(), "字符串:\"%s\"匹配\"%s\"，结果为%b",
                str, pattern, match(str, pattern)));
    }

    private static boolean match(String str, String pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        return matchCore(str, 0, pattern, 0);
    }

    private static boolean matchCore(String str, int sIndex, String pattern, int pIndex) {
        // 字符串结束，模式结束，匹配成功
        if (sIndex >= str.length() && pIndex >= pattern.length()) {
            return true;
        }
        // 字符未结束，模式结束，匹配失败
        if (sIndex < str.length() && pIndex >= pattern.length()) {
            return false;
        }
        // 字符串结束，模式未结束，继续
        // 字符串为结束，模式未结束，继续
        char first = pattern.charAt(pIndex);

        // 匹配任意一个字符
        if (first == '.') {
            return matchCore(str, sIndex + 1, pattern, pIndex + 1);
        } else {// first 为字符
            char second = '0';
            if (pIndex + 1 < pattern.length()) {
                second = pattern.charAt(pIndex + 1);
            }
            if (second == '*') {
                // first 匹配
                if (first == str.charAt(sIndex)) {// 分两种情况
                    // 第一种，匹配0个字符（字符串不动，模式走2步）
                    // 第二种，匹配1个字符（字符串走1步，模式走2步或不动）
                    return matchCore(str, sIndex, pattern, pIndex + 2)
                            || matchCore(str, sIndex + 1, pattern, pIndex + 2)
                            || matchCore(str, sIndex + 1, pattern, pIndex);
                } else {// 匹配失败
                    return matchCore(str, sIndex, pattern, pIndex + 2);
                }
            } else {// second 不为*
                // first 匹配
                if (sIndex < str.length() && first == str.charAt(sIndex)) {
                    return matchCore(str, sIndex + 1, pattern, pIndex + 1);
                } else {// 匹配失败
                    return false;
                }
            }
        }
    }

}
